package leetcode;

import java.util.Arrays;

public class ImplementStrStr {

	 public int strStr(String haystack, String needle) {
	        if(haystack==null||needle==null)return -1;
	        return haystack.indexOf(needle);
	 }
	 
	 public int[] getNext(String str){
		 int []preFix=new int[str.length()];
		 int i=0;
		 for(i=1;i<str.length();i++){
			 int k=preFix[i-1];
			 while(k!=0&&str.charAt(i)!=str.charAt(k))
				 k=preFix[k-1];
			 if(str.charAt(i)==str.charAt(k)){
				 k++;
				 preFix[i]=k;
			 }else{
				 preFix[i]=0;
			 }
		 }
		 return preFix;
	 }
	 
	 public int indexOf(String haystack,String needle){
		 
		int heyLength=haystack.length();
		int needLength=needle.length();
		int i=0;
		int j=0;
		while(i<heyLength&&j<needLength){
			if(haystack.charAt(i)==needle.charAt(j)){
				i++;
				j++;
			}else{
				i=i+1-j;
				j=0;
			}
		}
		if(j==needLength){
			return i-j;
		}else{
			return -1;
		}
	 }
	 
	 
	 public int indexOf2(String haystack,String needle){
		 
			int heyLength=haystack.length();
			int needLength=needle.length();
			if(needLength==0){
			    return 0;
			}
			int i=0;
			int j=0;
			int pre[]=getNext(needle);
			while(i<heyLength&&j<needLength){
				while(j>0&&haystack.charAt(i)!=needle.charAt(j)){
					 j = pre[j-1];
				}
				if(haystack.charAt(i)==needle.charAt(j)){
					j++;
				}
				
				i++;
			    if(j==needLength){
				 return i-j;
			    }
			}
			return -1;
		 }
	 
	 public static void main(String[] args) {
		ImplementStrStr i=new ImplementStrStr();
		System.out.println(i.indexOf2("abc", ""));
		System.out.println(i.indexOf2("a", "a"));
//		System.out.println(i.indexOf2("mississippi","pi"));
		System.out.println(i.indexOf2("abbababbabbbabaaab","abbabbbabaa"));
		System.out.println(Arrays.toString(i.getNext("issip")));
	}
}
